3.21
//Write routines to implement two stacks using only one array. 
//Your stack routines should not declare an overflow unless every slot in the array is used.
//功能Pop,Top,Size,IsEmpty,IsFull,Push,
typedef struct node
{
    int top[2], bottom[2];
    int *V;
    int size[2];
} NODE;
int InitStack(NODE *S, int Stack_Size)
{
    S = (NODE *)malloc(sizeof(NODE));
    S.V = (int *)malloc(Stack_Size * sizeof(int));
    S.top[0] = -1;
    S.bottom[0] = -1;
    S.size[0] = 0;
    S.top[1] = Stack_Size;
    S.bottom[1] = Stack_Size;
    S.size[1] = 0;
    return 0;
}
int IsFull(NODE *S)
{
    if (S.top[1] - S.top[0] == 1)
    {
        return 1; //栈满了
    }
    else
        return 0; //栈没有满
}
int IsEmpty(NODE *S)
{
    if (S.top[0] == S.bottom && S.top[1] == S.bottom[1])
    {
        return 1;//栈空
    }
    else return 0;//栈满
}
int Push(NODE *S,int e0, int e1)
{
    //e0进入0号栈，e1进入1号栈
    if(IsFull(S))
    {
        printf("Stack is Full!\n");
        return 0;//栈满，无法入栈
    }
    S.V[++S.top[0]] = e0;
    S.V[--S.top[1]] = e1;
    return 1;//如果成功进栈，返回值为1
}
int Pop(NODE *S, int &e0, int &e1)
{
    //e0返回0号栈的栈顶元素，e1返回1号栈的栈顶元素
    if(IsEmpty(S))
    {
        return 0;
    }
    e0 = S.V[S.top[0]--];
    e1 = S.V[S.top[0]++];
    return 1;
}



3.25
//Write the routines to implement queues usinga linked lists
//Pop,Front,Size,IsEmpty，Push
typedef struct node *Position;
typedef struct node{
    ElementType element;
    Position next;
}NODE;
Position CreateQueue(Node *queue)
{
    queue = (NODE *)malloc(sizeof(NODE));
    queue->next = NULL;
    return queue;
}
Position IsEmpty(NODE *queue)
{
    if ( !queue->next )
        return 1;   
    return 0;
}
ElementType Front(NODE *queue)
{
    if (IsEmpty(queue))
    {
        printf("Queue is empty!\n");
        return 0;
    }
    while(queue->next)
        queue = queue->next;
    return queue->element;
}
Position Push(NODE *queue, ElementType x)
{
    Position tmp = (NODE *)malloc(sizeof(NODE));
    tmp->element = x;
    tmp->next = queue->next;
    return queue;
}
int Pop(NODE *queue)
{
    if(IsEmpty(queue))
    {
        printf("The queue is empty!\n");
        return 0;
    }
    while(queue->next->next)
        queue = queue->next;
    NODE *tmp = queue->next;
    queue->next = NULL;
    free(tmp);
    return 1;
}




3.26
//deque的实现
//push(x,d),pop(d),inject(x,d),eject(d)
struct node{
    ElementType item;
    struct node *next;
};
typedef struct node Deque;
Deque* CreateDeque()
{
    Deque *d;
    d = (Deque*)malloc(sizeof(Deque));
    d->next = NULL;
    return d;
}
void Push(ElementType x, Deque d )
{
    Deque *tmp = (Deque*)malloc(sizeof(Deque));
    tmp->item = x;
    tmp->next = d->next;
    d->next = tmp;
    return ;
}
ElementType Pop(d)
{
    if (d->next==NULL)
    {
        printf("Invalit!\n");
        return 0;
    }
    return d->next->element;
}
void Inject(ElementType x, Deque d)
{
    while(d->next)
        d = d->next;
    d->next = (Deque*)malloc(sizeof(Deque));
    d->item = x;
    return;
}
ElementType Eject(Deque d)
{
    if(!d->next)
    {
        printf("Invalit!\n");
        return 0;
    }
    while (d->next->next)
        d = d->next;
    Deque *tmp = d->next;;
    ElementType item = tmp ->item;
    free(tmp);
    d->next = NULL;
    return item;
}